1. Field of the Invention
The present invention relates generally to communication networks. More specifically, the present invention relates to network routers and switches.
2. Description of the Background Art
Computer networks are widely used to provide increased computing power, sharing of resources and communication between users. Networks may include a number of computer devices within a room, building or site that are connected by a high-speed local data link such as Ethernet, token ring, or the like. Local area networks (LANs) in different locations may be interconnected to form a wide area network (WAN).
The Internet is an interconnected set of networks, wherein each of the constituent networks retains its identity, and special mechanisms are needed for communication across multiple networks. The constituent networks are referred to as subnetworks.
Each subnetwork in the Internet supports communication among the devices connected to that subnetwork. Routers are specialized computing devices that are typically used to connect two subnetworks that may or may not be similar. A router typically employs internet protocol (IP) to allow communication between hosts and routers through the routers present in the internet protocol network. IP provides a connectionless or datagram service between stations.
Routers generally use routing tables to direct packet traffic over a network. Routing tables have multiple entries, or routes, each route routes traffic to a single subnet. A subnet is identified by its network address and its width or network mask. Each route specifies forwarding information for the set of hosts that fall within that route's subnet. Each subnet may be further divided into smaller subnets. These subnets may be routed to using routes specific to the subdivided subnets, or there may be just one route that is used to route to a set of subnets contained within a larger subnet.
For example, in the Internet context, each entry consists of the 32-bit network (Internet Protocol) address such as “192.56.7.48” and a width, or prefix length, such as 8, 16, or 24 (these are not exclusive, the width may be any number from 0 to the number of bits in the address.) The width specifies how many bits a router should consider when comparing a destination to a route for the purpose of determining if that IP address falls within (or “matches” or “is contained by”) the route. For instance, if the route has a network address of “192.56.7.48” and a width of “16”, the router need only consider the first two bytes to determine if a particular IP address matches the route (in other words, falls within the subnet specified for the route) and may effectively read the network address as “192.56.0.0”.
Associated with each entry in the routing table is forwarding information. In some implementations, the forwarding information may comprise a “next hop” value that indexes into a second table. The second or “next hop” table is used to map layer 3 addresses to layer 2 forwarding information of adjacent routers and hosts. For instance, the IP address “192.56.7.48/16” may have an associated next hop value of “17”, meaning that the IP address and the layer 2 forwarding information for either the next hop router or for the host itself if the host is directly connected is at location 17 in the next hop table.
The router uses the routing table to select the path to use when routing a packet through the network. When a packet arrives at a router, the router first finds the route in the routing table that provides the best match to the destination address. Many routing systems use best match prefix for route selection. This rule dictates that the route that best matches the destination of a packet is the route to use for routing the packet. Using best match prefix, the route that “best” matches the packet is the route with the longest prefix and whose subnet contains the destination address. Packets are forwarded using the forwarding information associated with the route that best matches the destination address from the packet.
It is highly desirable to improve performance of routers and of networks in general. Conventionally, in order to increase router performance, either a very large (i.e. high performance) must be used, or multiple smaller (i.e. lower performance) routers may be interconnected together using routing protocols.
FIG. 1 is a schematic diagram depicting a conventional configuration 100 where multiple routers interconnected via routing protocols. In the example illustrated, three routers 102 are interconnected by way of a layer 3 network 104. In other words, the routers 102 utilize layer 3 routing protocols to communicate data packets between each other.